import java.util.Arrays;

/**
 * @program: sort
 * @author: JCM
 * @create: 2023-10-24 09:45
 * @description:
 **/
public class Main2 {
    public static void main(String[] args) {
        int[] arr = {4,3,5,2,6,1,7,9,8,0};
//        insertSort(arr);
//        shellSort(arr);
//        selectSort(arr);
//        bubbleSort(arr);
//        heapSort(arr);
//        quickSort(arr);
//        quickSort1(arr);
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    static void insertSort(int[] arr) {
        for(int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i;
            for(; j > 0; j--) {
                if(arr[j-1] > tmp ) {
                    arr[j] = arr[j-1];
                }else {
                    break;
                }
            }
            arr[j] = tmp;
        }
    }
    static void shellSort(int[] arr) {
        int gap = arr.length;
        gap /= 2;
        while(gap > 1) {
            shell(gap,arr);
            gap /= 2;
        }
        shell(1,arr);
    }
    static void shell(int gap, int[] arr) {
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-gap;
            for(; j >= 0; j -= gap) {
                if(arr[j] > tmp) {
                    arr[j+gap] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }

    static void selectSort(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            int tmp = arr[0];
            for(int j = 1; j < arr.length-i; j++) {
                if(arr[j] > tmp) {
                    tmp = arr[j];
                }else {
                    arr[j-1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

    static void bubbleSort(int[] arr) {
        for(int i = 0; i < arr.length; i++) {
            boolean flg = true;
            for(int j = 1; j < arr.length-i; j++) {
                if(arr[j] < arr[j-1]) {
                    int t = arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = t;
                    flg = false;
                }
            }
            if (flg) {
                break;
            }
        }
    }

    static void heapSort(int[] arr) {
        // 建堆
        createHeap(arr);
        // 排序
        int len = arr.length-1;
        while (len > 0) {
            int t = arr[len];
            arr[len] = arr[0];
            arr[0] = t;
            len--;
            shiftDown(0,arr,len);
        }
    }
    private static void createHeap(int[] arr) {
        for(int parent = (arr.length-1-1)/2; parent >= 0; parent--) {
            shiftDown(parent,arr,arr.length-1);
        }
    }
    private static void shiftDown(int parent, int[] arr, int length) {
        int child = parent*2+1;

        while (child <= length) {
            if(child+1 <= length && arr[child+1] > arr[child]) {
                child++;
            }
            if(arr[child] > arr[parent]) {
                int tmp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = tmp;
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }

    static void quickSort(int[] arr) {
        quick(arr, 0, arr.length-1);

    }
    private static void quick(int[] arr, int left, int right) {
        if(left >= right) return;
        int pivot = partitionHoare(arr,left,right);
        quick(arr,left,pivot);
        quick(arr,pivot+1,right);
    }
    private static int partitionHoare(int[] arr, int left, int right) {
        int start = left, end = right;
        while (start < end) {
            while (start < end && arr[end] >= arr[left]) {
                end--;
            }
            while (start < end && arr[start] < arr[left]) {
                start++;
            }
            int tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
        }
        int tmp = arr[start];
        arr[start] = arr[left];
        arr[left] = tmp;
        return left;
    }
    // 挖坑法，快排
    private static void quickSort1(int[] arr) {
        quick1(arr,0,arr.length-1);
    }
    private static void quick1(int[] arr, int left, int right) {
        if(left >= right) return;
        int pivot = partitionHole(arr,left,right);
        quick1(arr,left,pivot);
        quick1(arr,pivot+1,right);
    }
    private static int partitionHole(int[] arr, int left, int right) {
        int tmp = arr[left];
        int start = left, end = right;
        while(start < end) {
            while(start < end && arr[end] > tmp) {
                end--;
            }
            arr[start] = arr[end];
            while (start < end && arr[start] < tmp) {
                start++;
            }
            arr[end] = arr[start];
        }
        arr[start] = tmp;
        return  start;
    }

    private static void mergeSort(int[] arr) {
        // 先分开，再合并
        divided(arr,0,arr.length-1);
    }
    private static void divided(int[] arr,int start, int end) {
        if(start >= end) return;
        int pivot = (start+end)/2;
        divided(arr,start,pivot);
        divided(arr,pivot+1,end);
        // 合并
        merge(arr,start,end, pivot);
    }
    private static void merge(int[] arr, int start, int end, int mid) {
        int s1 = start, s2 = mid+1; // s1 是左边的起点，s2 是右边的起点
        // 需要一个新数组，暂时存放数据
        int[] tmp = new int[end-start+1];
        int k = 0;
        while(s1 <= mid && s2 <= end) {
            if(arr[s1] <= arr[s2]) {
                tmp[k++] = arr[s1++];
            }else {
                tmp[k++] = arr[s2++];
            }
        }
        while(s1 <= mid) {
            tmp[k++] = arr[s1++];
        }
        while (s2 <= end) {
            tmp[k++] = arr[s2++];
        }
        // 将 tmp 中的数据拷贝回原数组
        for(int i = 0; i < k; i++) {
            arr[i+start] = tmp[i];
        }
    }


}
